package LeetCodeHot100TopInterview;


public class Q096_DifferentBST {

    //给一个 n 判断 1->n 不同的二叉搜索树
    //需不需要建树 ==> 不需要
    // 1 -> n 升序
    public int numTrees(int n) {
        return process(n);
    }

    public int process(int n){
        if (n == 0 || n == 1){
            return 1;
        }
        int ans = 0;
        for (int i = n - 1; i > -1; i--) {
            //每个点都是右边比我大 左边比我小
            //n为根节点  我左边剩余 * 我右边剩余
            ans += process(i) * process(n - i - 1);
        }
        return ans;
    }



}
